//
//
#ifndef Sort_h__
#define Sort_h__

#include "Stdafx.h"

namespace Algorithm
{
	template<class Reference>
	void sortInsertion(Reference& _array, int _n)
	{
		typedef Reference::value_type data_type;
		for(int i = 1; i < _n; i++)
		{
			if(_array[i] < _array[i-1])
			{
				int j = i - 1;
				data_type tmp = _array[i];
				while((tmp < _array[j]) && j >= 0)
				{
					_array[j+1] = _array[j];
					j--;
				}
				// find the position
				_array[j+1] = tmp;
			}
		}
	}

	template<class Reference>
	void sortShell(Reference& _array, int _n)
	{
		typedef Reference::value_type data_type;
		int step = _n/2;

		while(step > 0)
		{
			// begin from _array[step] to _array[_n-1]
			for(int i = step; i < _n; i++)
			{
				if(_array[i] < _array[i-step])
				{
					data_type tmp = _array[i];
					int j = i - step;
					
					// find the position 
					while(j >= 0 && _array[j] > tmp)
					{
						_array[j+step] = _array[j];
						j = j - step;
					}
					_array[j+step] = tmp;
				}
			}
			// next step length
			step /= 2;
		}
	}

	template<class Reference>
	void sortSelection(Reference& _array, int _n)
	{
		typedef Reference::value_type data_type;
		for(int i = 0; i < _n / 2; i++)
		{
			// cur: present the index of min and max value 
			int cur_min = i;
			int cur_max = i;
			for(int j = i+1; j < _n-i; j++)
			{
				// min
				if(_array[j] < _array[cur_min])
				{
					cur_min = j;
				}
				// max
				if(_array[j] > _array[cur_max])
				{
					cur_max = j;
				}
			}
			
			// swap two element: _array[i] and _array[cur_min]
			if(i != cur_min)
			{
				data_type tmp = _array[cur_min];
				_array[cur_min] = _array[i];
				_array[i] = tmp;
			}

			// swap two element: _array[_n-1-i] and _array[cur_max]
			if(i != cur_max)
			{
				data_type tmp = _array[cur_max];
				_array[cur_max] = _array[_n-1-i];
				_array[_n-1-i] = tmp;
			}
		}
	}

	template<class Reference>
	void adjustHeap(Reference& _array, int _n, int _cur)
	{
		typedef Reference::value_type data_type;
			
		// heap tree index begin from 1 to n
		// but array index begin from 0 to n-1
		int lchild = 0;
		int rchild = 0;
		int i = _cur;
		int max_index = _cur;
		
		while(i <= _n/2)
		{
			lchild = i * 2;
			rchild = i * 2 + 1;
			
			// find max value in left or right child
			if(lchild <= _n)
			{
				if(_array[lchild-1] > _array[max_index-1])
				{
					max_index = lchild;
				}
			}
			if(rchild <= _n)
			{
				if(_array[rchild-1] > _array[max_index-1])
				{
					max_index = rchild;
				}
			}
			
			// need adjust
			if(max_index != i)
			{
				// swap value: _array[i] and _array[max_index]
				data_type tmp = _array[i-1];
				_array[i-1] = _array[max_index-1];
				_array[max_index-1] = tmp;

				// adjust sub-heap
				i = max_index;
			}
			else
			{
				// adjust finish
				break;
			}
		}
	}


	template<class Reference>
	void sortHeap(Reference& _array, int _n)
	{
		typedef Reference::value_type data_type;

		// build heap
		for(int i = _n/2; i >= 1; i--)
		{
			adjustHeap(_array, _n, i);
		}

		// adjust heap
		for(int i = _n; i >= 1	; i--)
		{
			// swap value: _array[i-1] and _array[0]
			data_type tmp = _array[i-1];
			_array[i-1] = _array[0];
			_array[0] = tmp;
			// adjust the remain heap 
			adjustHeap(_array, i-1, 1);
		}
	}

	template<class Reference>
	void sortBubble(Reference& _array, int _n)
	{
		typedef Reference::value_type data_type;
		for(int i = 0; i < _n; i++)
		{
			for(int j = _n-1; j > i; j--)
			{
				if(_array[j] < _array[j-1])
				{
					data_type tmp = _array[j];
					_array[j] = _array[j-1];
					_array[j-1] = tmp;
				}
			}
		}
	}

	template<class Reference>
	void sortQuick(Reference& _array, int _left, int _right)
	{
		typedef Reference::value_type data_type;
		if(_left < _right)
		{
			int i = _left;
			int j = _right;

			data_type tmp = _array[_left];
			while(i < j)
			{
				// find a _array[j] > tmp
				while(i < j && tmp < _array[j])
				{
					j--;
				}
				if(i < j)
				{
					_array[i++] = _array[j];
				}

				// find a _array[j] < tmp
				while(i < j && tmp > _array[i])
				{
					i++;
				}
				if(i < j)
				{
					_array[j--] = _array[i];
				}
			}

			// condition: i==j
			_array[i] = tmp;
			sortQuick(_array, _left, i-1);
			sortQuick(_array, i+1, _right);
		}
	}
}

#endif